package 力扣;

/**

 给定一个非空二叉树，返回其最大路径和。
 本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
         示例 1：
         输入：[1,2,3]
         1
         / \
         2   3
         输出：6
         示例 2：
         输入：[-10,9,20,null,null,15,7]
         -10
         / \
         9  20
           /  \
          15   7

         输出：42
 */

public class _124二叉树中的最大路径和 {


    /**
     对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:
     1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
     2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径
     **/
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    int ret = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        getMax(root);
        return ret;
    }

    private int getMax(TreeNode root) {
        if( root == null ) return 0;
        int left = Math.max(0,getMax(root.left));// 最小值为0 ,因为为负数的话，直接舍弃
        int right = Math.max(0,getMax(root.right));
        ret = Math.max(ret,left+right+root.val);
        return Math.max(left,right)+root.val;
    }
}
